1. Field of the Invention
The present invention relates generally to the field of machine perception and more particularly to calculating probable positions in three dimensions of occluded surfaces of viewed objects.
2. Description of the Prior Art
The present invention relates to viewing an object and constructing a 3-dimensional (3D) map of the surface of object, including determining probable maps of those surfaces of the object that are obscured, hidden, or otherwise occluded from the view. In many applications it is necessary or desirable to have such a 3D model of an object. Such applications include computer-aided design, computer-aided manufacturing, electronic commerce, robotics, and digital entertainment. Conventionally, a 3D model of an object is constructed by acquiring images or range data of the object from multiple, widely separated viewpoints. The multiple viewpoints are chosen so that every side of the object is included in images from one or more of the viewpoints. The information from these multiple viewpoints is combined by well-known techniques to create the 3D model.
However, in certain applications, it is either not possible or not economical to view the object from multiple viewpoints, and in some instances even if multiple viewpoints are used, some surfaces still remain occluded. For example, if a robotic system consisting of an arm and a hand is employed to pick and pack unknown objects, the robotic system must determine enough surface information about the unknown objects to plan stable grasps. Cost, physical constraints, or other constraints can limit the number of vision sensors, so that the objects can be viewed only from one perspective. In these situations, surfaces that do not face the vision sensors are hidden from view by the objects themselves. Such surfaces are referred to as being “self-occluded.”
Grasping an object with a typical robotic end-effector requires surfaces in a generally opposing relationship. For example, to grasp an object with a parallel-jawed gripper, the object must have a pair of opposing parallel surfaces. Mechanical hands with multiple fingers can grasp objects without parallel contact surfaces, but still require some kind of opposition of the surfaces. An image taken from a single viewpoint provides a description of only some of the surfaces. Using only visible surfaces acquired from a single viewpoint, most desirable grasps cannot be planned, due to a lack of information about one or more of the possibly useful contact surfaces. Hence, for planning a grasp of an object, it is desirable to be able to compute probable surfaces for self-occluded regions.
Additionally, regions of the object may be blocked from a viewing position by the presence of other objects. We refer to such regions as “intra-occluded.” Intra-occluded regions present problems similar to those created by self-occlusion. They also cannot be used for grasp planning and thereby limit the kinds of grasps that can be considered in the plan. Hence, it is also desirable to be able to compute probable surfaces for intra-occluded regions.
In other applications, it may be possible to view an object from several sides, but not all sides. Using standard image processing techniques the images from the several visible sides may be composed to obtain a partial surface model that is more complete than one obtained from only a single viewpoint, yet one that is not entirely complete. Here, too, it is desirable to be able to use the partial model to compute probable surfaces for the regions that remain occluded.
In certain applications, it may be desirable or necessary to confirm the probable surfaces using additional sensors. For example, the fingers of the hands may be equipped with force, tactile, or proximity sensors. Alternatively, a camera may be mounted on the end of the arm located to view the surfaces to be grasped. However, even when such additional sensors are present, efficient operation requires that the initial grasping plan made without their sensor readings is correct with high probability.
Hence, in a variety of diverse situations, it is desirable to compute probable surfaces in occluded regions given only the position information from a limited number of viewpoints.
Heretofore, using 3D models of visible surfaces to create 3D models of occluded surfaces has not been addressed. Rather, research has been limited to determining symmetries within 2D and 3D images, and to modeling 3D surfaces from 2D images.
A large number of papers in the scientific literature deal with symmetries in 2D images. For example, D. Shen, H. H. S. Ip, K. K. T. Cheung, and E. K. Teoh, “Symmetry Detection by Generalized Complex (GC) Moments: A Close-Form Solution,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 21, No. 5, May 1999 describes how symmetries may be detected in 2D images and cites many earlier papers on this topic. Another paper, A. Blake, M. Taylor, and A. Cox, “Grasping Visual Symmetry,” International Conference on Computer Vision, pp 724-733, May 1993, shows how 2D symmetries and anti-symmetries may be used to plan grasps of planar objects by grasping around the rim.
There have also been many papers discussing how 3D shapes can be reconstructed from 2D images. A paper by T. Kanade, “Recovery of the three-dimensional shape of an object from a single view,” Artificial Intelligence, Volume 17, Issues 1-3, August 1981, pp 409-460 is a relatively early paper on this topic. Another paper by H. Mitsumoto, S. Tamura, K. Okazaki, N. Kajimi, and Y. Fukui, “3-D Reconstruction Using Mirror Images Based on a Plane Symmetry Recovery Method,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 14, No. 9, September 1992, pp 941, 946 uses a 2D image that contains both an image of an object and an image of that object as reflected by one or more physical mirrors to perform a 3D reconstruction of the visible surfaces of the object. A recent paper by F. Han and S. C. Zhu, “Bayesian inference of 3D scene from a single images,” Proc. of Int'l Workshop on High-Level Knowledge in 3D Modeling and Motion, Nice France, 2003 infers plausible occluded surfaces from a computed primal sketch of a 2D image. Another paper by H. Zabrodsky, D. Weinshall, “Using Bilateral Symmetry to Improve 3D Reconstruction from Image Sequences,” Computer Vision and Image Understanding: CVIU, Vol. 67, No. 1, pp 48 to 57, 1997 finds symmetries in 2D images and uses those symmetries to improve reconstructions of visible features in a technique known as “structure from motion.” Additionally, two papers by D. Terzopoulos et al., “Symmetry-Seeking Models and 3D Object Reconstruction,” International Journal of Computer Vision, 1, pp 211-221, 1987 and “Constraints on Deformable Models: Recovering 3D Shape and Nonrigid Motion,” Artificial Intelligence, 36 (1988) pp 91-123 reconstruct objects having a generalized axial symmetry from 2D data using manual initialization; in the 1988 paper, multiple sets of 2D data are used to obtain 2D outlines from multiple viewpoints.
However, techniques based on 2D images can make only limited use of symmetries to perform 3D reconstructions. This is because a 2D projection distorts 3D symmetries. Accordingly, the relationship between a 3D symmetry of an object and the observed projected 2D image is complex and subject to ambiguity. Hence, research considering 2D images does not address the problems solved by this invention.
There has been less work on the topic of symmetry in 3D data. A paper by C. Sun and J. Sherrah, “3D Symmetry Detection Using the Extended Gaussian Image,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 19, No. 2, February 1997, pp 164-169 describes how 3D symmetries that are global to an object may be detected by converting the problem to the correlation of a Gaussian image. A paper by R. Zabrodsky, S. Peleg, and D. Avnir, “Symmetry as a Continuous Feature,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 12, pp. 1,154-1,166, December 1995 defines a continuous symmetry measure to quantify the symmetry of both 2D and 3D objects; the paper applies this measure to finding the orientation of 3D symmetries. Another paper by M. Kazhdan et al., “A Reflexive Symmetry Descriptor,” European Conference on Computer Vision, 2002, pp 642-656 describes how mirror symmetries that are global to an object can be detected in a 3D voxel model of the object. However, none of these papers addresses the problem of reconstructing occluded 3D surfaces from 3D data.
Hence, there is a need for a system and method able to reconstruct probable occluded surfaces from 3D data.